package com.test.daily.leetcode.y2022.m07.day0718.v05;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Tom on 2022/7/18
 */
public class Solution {
    public static class Node{
        int value;
        public Node left;
        public Node right;
    }
    public boolean isBST(Node head){
        List<Node> list = new ArrayList<>();
        in(head, list);
        for (int i = 1; i < list.size(); i++) {
            if(list.get(i).value <= list.get(i-1).value){
                return false;
            }
        }
        return true;
    }
    public void in(Node head, List<Node> list){
        if(head == null){
            return;
        }
        in(head.left, list);
        list.add(head);
        in(head.right, list);
    }
    public static class Info{
        int max;
        int min;
        boolean isBST;
        public Info(int max, int min, boolean isBST){
            this.max = max;
            this.min = min;
            this.isBST = isBST;
        }
    }
    public boolean isCBT2(Node head){
        return process(head).isBST;
    }
    public Info process(Node head){
        if(head == null){
            return null;
        }
        Info leftInfo = process(head.left);
        Info rightInfo = process(head.right);
        int max = head.value;
        if(leftInfo != null){
            max = Math.max(max, leftInfo.max);
        }
        if(rightInfo != null){
            max = Math.max(max, rightInfo.max);
        }
        int min = head.value;
        if(leftInfo != null){
            min = Math.min(min, leftInfo.min);
        }
        if(rightInfo != null){
            min = Math.min(min, rightInfo.min);
        }
        boolean isBST = true;
        if(leftInfo != null && !leftInfo.isBST){
            isBST = false;
        }
        if(rightInfo != null && !rightInfo.isBST){
            isBST = false;
        }
        if(leftInfo != null && leftInfo.max > head.value){
            isBST = false;
        }
        if(rightInfo != null && rightInfo.min < head.value){
            isBST = false;
        }
        return new Info(max, min, isBST);
    }
}
